'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-09 11:15:59
LastEditTime: 2025-09-09 20:39:44
'''



# 最大矩形

class Solution:

    def largestRectangleArea(self, heights):
        n = len(heights)
        # left = [-1] * n
        # right = [n] * n
        st = []
        ans = 0
        for right, h  in enumerate(heights):
            
            # 找到左右边界 
            # 栈中保持 非递减 顺序
            while len(st) > 1 and heights[st[-1]] >= h:
                # 找到所有右边界！
                i = st.pop()
                left = st[-1]
                # 会弹出很多i
                ans = max(ans, heights[i] * (right - left - 1))
            
            # if st:

            #     left[i] = st[-1]
            
            st.append(right)


        
        # # 找到矩形的最大面积
        # for h, l, r in zip(heights, left, right):
        #     ans = max(ans, h * (r - l -1))

        return ans
        


if __name__ == "__main__":

    heights = [2,1,5,6,2,3]

    sol = Solution()

    res = sol.largestRectangleArea(heights)
    print(res)

